#include <bits/stdc++.h>

using namespace std;

const int maxn=10005;
const int maxm=10005;

int seq[maxn],nums[maxn+maxm],cnums;
struct S{
    int sum,l,r;
}seg[maxn*250];
struct Q{
    char typ;
    int x,y,z;
}qry[maxm];
int bit_l[maxn],bit_r[maxn],rt[2*maxn],cl,cr;
int dest,isrt_val,cseg,n;

inline int lowbit(const int &x){return x&(-x);}
void build(int &cur,const int &old,const int &l,const int &r){
    cur=++cseg;
    S &s=seg[cur];
    s=seg[old];
    if(l!=r){
        int mid=(l+r)>>1;
        if(dest<=mid) build(s.l,seg[old].l,l,mid);
        else build(s.r,seg[old].r,mid+1,r);
        s.sum=seg[s.l].sum+seg[s.r].sum;
    }else s.sum++;
}
void isrt(int &cur,const int &l,const int &r){
    if(!cur) cur=++cseg;
    S &s=seg[cur];
    if(l!=r){
        int mid=(l+r)>>1;
        if(dest<=mid) isrt(s.l,l,mid);
        else isrt(s.r,mid+1,r);
        s.sum=seg[s.l].sum+seg[s.r].sum;
    }else s.sum+=isrt_val;
}
int query(int l,int r,int k){
    while(l<r){
        int sum=0;
        int mid=(l+r)>>1;
        for(int i=0;i<cl;i++) sum-=seg[seg[bit_l[i]].l].sum;
        for(int i=0;i<cr;i++) sum+=seg[seg[bit_r[i]].l].sum;
        if(k<=sum){
            r=mid;
            for(int i=0;i<cl;i++) bit_l[i]=seg[bit_l[i]].l;
            for(int i=0;i<cr;i++) bit_r[i]=seg[bit_r[i]].l;
        }else{
            k-=sum;
            l=mid+1;
            for(int i=0;i<cl;i++) bit_l[i]=seg[bit_l[i]].r;
            for(int i=0;i<cr;i++) bit_r[i]=seg[bit_r[i]].r;
        }
    }
    return l;
}

char str[20];

int main(){
    int m,T;

    //scanf("%d",&T);
    T=1;
    while(T--){
        scanf("%d%d",&n,&m);
        memset(seg,0,sizeof(seg));
        memset(rt,0,sizeof(rt));
        cnums=0;cseg=0;
        for(int i=1;i<=n;i++) scanf("%d",seq+i),nums[cnums++]=seq[i];
        for(int i=1;i<=m;i++){
            scanf("%s%d%d",str,&qry[i].x,&qry[i].y);
            qry[i].typ=*str;
            if(*str=='Q') scanf("%d",&qry[i].z);
            else nums[cnums++]=qry[i].y;
        }
        sort(nums,nums+cnums);
        cnums=unique(nums,nums+cnums)-nums;
        for(int i=1;i<=n;i++) seq[i]=lower_bound(nums,nums+cnums,seq[i])-nums+1;
        for(int i=1;i<=m;i++) if(qry[i].typ=='C') qry[i].y=lower_bound(nums,nums+cnums,qry[i].y)-nums+1;

        for(int i=1;i<=n;i++){
            dest=seq[i];
            build(rt[n+i],rt[n+i-1],1,cnums);
        }
        for(int i=1;i<=m;i++){
            if(qry[i].typ=='C'){
                dest=seq[qry[i].x];
                isrt_val=-1;
                for(int x=qry[i].x;x<=n;x+=lowbit(x)) isrt(rt[x],1,cnums);
                seq[qry[i].x]=qry[i].y;
                dest=qry[i].y;
                isrt_val=1;
                for(int x=qry[i].x;x<=n;x+=lowbit(x)) isrt(rt[x],1,cnums);
            }else{
                cl=cr=1;
                bit_l[0]=qry[i].x-1?rt[qry[i].x-1+n]:0; bit_r[0]=rt[qry[i].y+n];
                for(int x=qry[i].x-1;x>0;x-=lowbit(x)) bit_l[cl++]=rt[x];
                for(int y=qry[i].y;y>0;y-=lowbit(y)) bit_r[cr++]=rt[y];
                printf("%d\n",nums[query(1,cnums,qry[i].z)-1]);
            }
        }
    }
    return 0;
}
